package com.sjc.algorithm.job;

import java.util.HashMap;

/**
 * 缓存删除策略
 * LRU：最近最少使用， 内存管理算法。
 * 长期不被使用的数据， 在未来被用到的几率也不大
 * 哈希链表
 * @author by SangJiacun
 * @Date 2020/5/14 14:50
 */
public class MyLRU {

    private Node head;
    private Node end;
    private int limit;

    private HashMap<String,Node> hashMap;

    public MyLRU(int limit){
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    public String get(String key){
        Node node = hashMap.get(key);
        if(null == node){
            return null;
        }

        refreshNode(node);
        return node.value;
    }

    public void put(String key,String value){
        Node node = hashMap.get(key);
        if(null == node){
            if(hashMap.size() >= limit){
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node = new Node(key,value);
            addNode(node);
            hashMap.put(key,node);
        }else{
            node.value = value;
            refreshNode(node);
        }
    }

    public void remove(String key){
        Node node = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }

    /**
     * 刷新被访问的节点位置
     * @param node
     */
    private void refreshNode(Node node){
        if(node == end){
            return;
        }
        removeNode(node);
        addNode(node);
    }

    /**
     * 移除节点
     * @param node
     * @return
     */
    private String removeNode(Node node){
        if(node == head && node == end){
            head = null; end = null;
        }else if(node == end){
            // 移除尾结点
            end = end.pre;
            end.next = null;
        }else if(node == head){
            // 移除头结点
            head = head.next;
            head.pre = null;
        }else{
            // 移除中间节点
            node.pre.next  = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 增加节点
     * @param node 尾部插入节点
     */
    private void addNode(Node node){
        if(end != null){
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if(head == null){
            head = node;
        }
    }

    /**
     * 哈希链表，双向链表
     */
    private static class Node{
        private String key;
        private String value;
        private Node next;
        private Node pre;

        public Node(String key, String value){
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        MyLRU lru = new MyLRU(5);
        lru.put("01","用户1信息");
        lru.put("02","用户2信息");
        lru.put("03","用户3信息");
        lru.put("04","用户4信息");
        lru.put("05","用户5信息");
        lru.get("02");

        lru.put("04","用户4信息更新");
        lru.put("06","用户6信息");

        System.out.println(lru.get("01")); //null
        System.out.println(lru.get("06"));
    }
}
